Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Кафедра ПЗ
КУРСОВА РОБОТА
з курсу: “Методи та засоби комп’ютерних інформаційних технологій”
СТИСНЕННЯ ІНФОРМАЦІЇ МЕТОДОМ ХАФФМАНА
ЗМІСТ
ЗМІСТ 2
ВСТУП 2
ПОСТАНОВКА ЗАВДАННЯ 3
1. АНАЛІТИЧНИЙ РОЗДІЛ 3
1.1 Способи стиснення інформації 3
1.2. Алгоритм RLE 4
1.3. Алгоритм KWE 5
1.4. Алгоритм Хаффмана 6
2. ІСНУЮЧІ АНАЛОГИ 8
2.1 WinRar 8
2.2 WinZip 10
3.ПРОЕКТНИЙ РОЗДІЛ 12
3.1. Структури даних для методу Хаффмана 12
3.2. Швидший алгоритм побудови дерева 13
3.3. Алгоритм обчислення кодів Хаффмана 13
3.4. Розмір і формат запису упакованих даних 14
3.5. Кодування даних 15
3.6. Декодування даних 16
4. ІНТЕРФЕЙС ПРОГРАМИ 17
5. ТЕКСТ ПРОГРАМИ 18
6. ЕКСПЕРИМЕНТАЛЬНИЙ РОЗДІЛ 30
Таблиця порівняння стиску файлів різних форматів 31
ВИСНОВОК 31
Використана література 33
ВСТУП
Характерною особливістю більшості типів даних є їх надлишковість. Ступінь надлишковості даних залежить від типу даних. Наприклад, для відеоданих ступінь надлишковості в декілька разів більша ніж для графічних даних, а ступінь надлишковості графічних даних, у свою чергу, більша за ступінь надлишковості текстових даних. Іншим фактором, що впливає на ступінь надлишковості є прийнята система кодування. Прикладом систем кодування можуть бути звичайні мови спілкування, які є ні чим іншим, як системами кодування понять та ідей для висловлення думок. Так, встановлено, що кодування текстових даних за допомогою засобів української мови дає в середньому надлишковість на 20-25% більшу ніж кодування аналогічних даних засобами англійської мови.
Для людини надлишковість даних часто пов'язана з якістю інформації, оскільки надлишковість, як правило, покращує зрозумілість та сприйняття інформації. Однак, коли мова йде про зберігання та передачу інформації засобами комп'ютерної техніки, то надлишковість відіграє негативну роль, оскільки вона приводить до зростання вартості зберігання та передачі інформації. Особливо актуальною є ця проблема у випадку необхідності обробки величезних обсягів інформації при незначних об'ємах носіїв даних. У зв'язку з цим постійно виникає проблема позбавлення надлишковості або стиснення даних. Коли методи стиснення даних застосовуються до готових файлів, то часто замість терміну "стиснення даних" вживають термін "архівування даних", стиснений варіант даних називають архівом, а програмні засоби, що реалізують методи стиснення називаються архіваторами.
В залежності від того, в якому об'єкті розміщені дані, що підлягають стисненню розрізняють:
Стиснення (архівування) файлів: використовується для зменшення розмірів файлів при підготовці їх до передавання каналами зв'язку або до транспортування на зовнішніх носіях малої ємності;
Стиснення (архівування) папок: використовується як засіб зменшення обсягу папок перед довготерміновим зберіганням, наприклад, при резервному копіюванні;
Стиснення (ущільнення) дисків: використовується для підвищення ефективності використання дискового простору шляхом стиснення даних при записі їх на носії інформації (як правило, засобами операційної системи).
ПОСТАНОВКА ЗАВДАННЯ
Написати програму на об’єктно-орієнтованій мові програмування для стиснення даних за методом Хаффмана.Програма повинна кодувати та декодувати дані.
АНАЛІТИЧНИЙ РОЗДІЛ
1.1 Способи стиснення інформації
Існує багато практичних алгоритмів стиснення даних, але всі вони базуються на трьох теоретичних способах зменшення надлишковості даних. Перший спосіб полягає в зміні вмісту даних, другий - у зміні структури даних, а третій - в одночасній зміні як структури, так і вмісту даних.
Якщо при стисненні даних відбувається зміна їх вмісту, то метод стиснення є незворотнім, тобто при відновленні (розархівуванні) даних з архіву не відбувається повне відновлення інформації. Такі методи часто називаються методами стиснення з регульованими втратами інформації. Зрозуміло, що ці методи можна застосовувати тільки для таких типів даних, для яких втрата частини вмісту не прив...
